// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

// 你可以假设数组中无重复元素

// 双指针法

var searchInsert = function(nums, target) {
    let l = 0;
    let r = 1;
    if (target <= nums[l]) { return 0 };
    if (target > nums[nums.length - 1]) { return nums.length }
    if (target == nums[nums.length - 1]) { return nums.length - 1 }
    while (r < nums.length) {
        if (nums[l] == target) {
            return l;
        }
        if (nums[l] < target && target < nums[r]) {
            return r;
        }
        l++;
        r++;
    }
};

// 二分查找法
var searchInsert = function(nums, target) {
    if (target > nums[nums.length - 1]) {
        return nums.length;
    }
    if (target <= nums[0]) {
        return 0;
    }

    let left = 0;
    let right = nums.length;

    while (left <= right) {
        let mid = left + ((right - left) >> 1);
        if (target == nums[mid]) {
            return mid;
        } else if (target < nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};